#include"Sort.h"

void _incoSSort(int* arr, int begin, int end, int* tmp)
{
	if (begin == end)
		return;
	int mid = (begin + end) / 2;
	
	_incoSSort(arr, begin, mid, tmp);
	_incoSSort(arr, mid+1, end , tmp);
	
	
		int begin1 = begin;  int end1 = mid;
		int begin2 = mid + 1;  int end2 = end;
		int n = begin;
		while (begin1 <= end1 && begin2 <= end2)
		{
			if (arr[begin1] < arr[begin2])
			{
				tmp[n++] = arr[begin1++];
			}
			else
			{
				tmp[n++] = arr[begin2++];
			}
		}
		while (begin1 <= end1)
		{
			tmp[n++] = arr[begin1++];
		}
		while (begin2 <= end2)
		{
			tmp[n++] = arr[begin2++];
		}

	memcpy(arr+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}

void IncoSSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("tmp");
		return;
	}
	_incoSSort(arr, 0, n - 1, tmp);
	//memcpy(arr, tmp, sizeof(int) * n);

	free(tmp);
}